import java.util.Arrays;

public class Test4 {
    //利用双指针将数组里的元素分为非零在前，零在后
    //例如：{1，0，6，0，2，3，0，9}->{1,6,2,3,9,0,0,0}
    public void moveZeroes(int[] num){
        for (int cur = 0,dest=-1; cur < num.length; cur++) {
            if (num[cur]!=0){
                dest++;
                swap(num,cur,dest);
            }
        }
    }

    private void swap(int[] num, int cur, int dest) {
        int tmp=num[cur];
        num[cur]=num[dest];
        num[dest]=tmp;
    }

    public static void main1(String[] args) {
        int[] array={1,0,6,0,2,3,0,9};
        Test4 test4=new Test4();
        test4.moveZeroes(array);
    }
    //利用双指针复写零
    //如果数组中的数不为零，就复写一遍，遇到零就复写两次，当然这两个操作都要在数组长度内进行复写
    //例如：{1,0,2,3,0,4,0,5}->{1,0,0,2,3,0,0,4}  {1,0,2,3,0,4}->{1,0,0,2,3,0}
    public void duplicateZeroes(int[] arr){
        //1.先找到最后一个要复写的数（利用双指针去找最后一个要复写的数字）
        int cur=0;
        int dest=-1;
        while (cur<arr.length){
            if (arr[cur]!=0){
                dest++;
            }else {
                dest+=2;
            }
            //去看dest是否走完了
            if (dest>=arr.length-1){
                break;
            }
            cur++; //此时cur所指的位置的数就是最后一个需要复写的数
        }
        //单独处理边界情况
        if (dest== arr.length){
            arr[arr.length-1]=0;
            dest-=2;
            cur--;
        }
        //从后往前进行复写
        while (cur>=0){
            if (arr[cur]!=0){
                arr[dest--]=arr[cur--];
            }else {
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
        }
    }

    public static void main2(String[] args) {
        int[] array={1,0,2,3,0,4,0,5};
        int[] array2={1,0,2,3,0,4};
        Test4 test4=new Test4();
        test4.duplicateZeroes(array2);
    }
    //给你一个数，判断它是不是快乐数
    public int bitSum(int n){
        //首先定义一个sum去保存我数字每一位的平方和
        int sum=0;
        while (n!=0){
            //定义一个变量t，保存我给的数字的每一位
            int t=n%10;
            sum+=t*t;
            //将已经平方和的数字去掉
            n/=10;
        }
        return sum;
    }
    public boolean isHappy(int n){
        //定义出快指针和慢指针
        int slow=n;
        int fast=bitSum(n);
        while (slow!=fast){
            //慢指针走一步
            slow=bitSum(slow);
            //快指针走两步
            fast=bitSum(bitSum(fast));
        }
        return slow==1;
    }

    public static void main3(String[] args) {
        Test4 test4=new Test4();
        boolean happy = test4.isHappy(7);
        System.out.println(happy);
    }
    //盛最多水的容器
    public int maxArea(int[]height){
        int left=0;
        int right= height.length-1;
        int ret=0; // 用来保存每一次计算出来的体积
        while (left<right){
            int v=Math.min(height[left],height[right] )*(right-left); //计算出当前left与right所围成的体积
            ret=Math.max(ret,v);
            if (height[left]<height[right]){
                left++;
            }else {
                right--;
            }
        }
        return ret;
    }
    //寻找有效三角形的个数
    public int triangleNum(int[] arr){
        //首先对数组进行从小到大的排序
        Arrays.sort(arr);
        //固定数组里面最大的那个数（这里先固定最大的数，后续最大的数会依次减小，直到减到下标为2）
        int ret=0; //保存有效三角形的个数
        for (int i = arr.length-1;i >=2; i--) {
            int left=0;
            int right=i-1;
            while (left<right){
                if (arr[left]+arr[right]>arr[i]){
                    ret+=right-left;
                    right--;
                }else {
                    left++;
                }
            }
        }
        return ret;
    }

    public static void main4(String[] args) {
        Test4 test4=new Test4();
        int[]array={2,2,3,4,5};
        int num = test4.triangleNum(array);
        System.out.println(num);
    }
    //两数之和，给定一个数组，再给定一个目标值target,在给定的数组里面找出两个数，这两个数之和等于target,最后将找到的数以数组的形式返回即可
    public int[] twoSum(int[] array,int target){
        int left=0;
        int right= array.length-1;
        while (left<right){
            if (array[left]+array[right]<target){
                left++;
            }else if(array[left]+array[right]>target){
                right--;
            }else {
              return new int[]{array[left], array[right]};
            }
        }
        //照顾编译器，随便给个值即可
        //因为走else语句才有返回值，如果没有找到那两个值，就直接出while循环，这时编译器检查到没有返回值，而我们定义函数时，说明了返回类型是int[]类型
        //这时与我们事先定义好的方法出现了冲突，编译器就会报错
        return new int[]{1};
    }

    public static void main(String[] args) {
        Test4 test4=new Test4();
        int[] ay={1,4,5,6,7};
        int[] au=test4.twoSum(ay,13);
        for (int i = 0; i < au.length; i++) {
            System.out.println(au[i]);
        }
    }
}
